BZOJ2733【HNOI2012】永无乡 <并查集+线段树合并>

Problem

【HNOI2012】永无乡

Description

永无乡包含座岛，编号从到，每座岛都有自己的独一无二的重要度，按照重要度可以将这座岛排名，名次用到来表示。
某些岛之间由巨大的桥连接，通过桥可以从一个岛到达另一个岛。如果从岛出发经过若干座（含座）桥可以到达岛，则称岛和岛是连通的。
现在有两种操作：
：表示在岛与岛之间修建一座新桥。
：表示询问当前与岛连通的所有岛中第重要的是哪座岛，即所有与岛连通的岛中重要度排名第小的岛是哪座，请你输出那个岛的编号。

Input

第一行是用空格隔开的两个正整数和，分别表示岛的个数以及一开始存在的桥数。
接下来的一行是用空格隔开的个数，依次描述从岛到岛的重要度排名。
随后的行每行是用空格隔开的两个正整数和，表示一开始就存在一座连接岛和岛的桥。
后面剩下的部分描述操作。
该部分的第一行是一个正整数，表示一共有个操作。
接下来的行依次描述每个操作，操作的格式如上所述，以大写字母或开始，后面跟两个不超过的正整数，字母与数字以及两个数字之间用空格隔开。

Output

对于每个操作都要依次输出一行，其中包含一个整数，表示所询问岛屿的编号。
如果该岛屿不存在，则输出。

Sample Input

Sample Output

HINT

对于的数据，
对于的数据，

标签：并查集 线段树合并

Solution

线段树合并裸题。

只建桥不拆桥，可以用并查集维护是否在同一连通块内，在每个连通块内维护一棵值域线段树，这样可以查第小。对于建桥的操作，用并查集找出是那两个块合并到一起，将两个块内的线段树合并起来。

线段树合并只需要用函数式线段树动态开点，并像可并堆那样递归合并即可。

Code

#include <bits/stdc++.h>
#define MAX_N 100000
#define mid ((s+t)>>1)
using namespace std;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, m, a[MAX_N+5], b[MAX_N+5];
int sz, rt[MAX_N+5], fa[MAX_N+5];
struct node {int ls, rs, val;} tr[MAX_N*20];
int getf(int x) {return fa[x] == x ? x : fa[x] = getf(fa[x]);}
void modify(int &v, int s, int t, int p) {
    if (!v) v = ++sz;
    if (s == t) {tr[v].val++; return;}
    if (p <= mid) modify(tr[v].ls, s, mid, p);
    if (p >= mid+1) modify(tr[v].rs, mid+1, t, p);
    tr[v].val = tr[tr[v].ls].val+tr[tr[v].rs].val;
}
int query(int v, int s, int t, int k) {
    if (s == t) return s; int lsz = tr[tr[v].ls].val;
    if (lsz >= k) return query(tr[v].ls, s, mid, k);
    return query(tr[v].rs, mid+1, t, k-lsz);
}
int merge(int x, int y) {
    if (!x) return y; if (!y) return x;
    tr[x].ls = merge(tr[x].ls, tr[y].ls);
    tr[x].rs = merge(tr[x].rs, tr[y].rs);
    tr[x].val = tr[tr[x].ls].val+tr[tr[x].rs].val;
    return x;
}
int main() {
    read(n), read(m);
    for (int i = 1; i <= n; i++) read(a[i]), b[a[i]] = i, fa[i] = i;
    for (int i = 1, u, v; i <= m; i++)
        read(u), read(v), u = getf(u), v = getf(v), fa[v] = u;
    for (int i = 1; i <= n; i++) modify(rt[getf(i)], 1, n, a[i]);
    int T; read(T);
    while (T--) {
        char opt[2]; scanf("%s", opt);
        if (opt[0] == 'B') {
            int x, y; read(x), read(y), x = getf(x), y = getf(y);
            if (x^y) fa[y] = x, rt[x] = merge(rt[x], rt[y]);
        } else {
            int x, k; read(x), read(k);
            if (tr[rt[x = getf(x)]].val < k) puts("-1");
            else printf("%d\n", b[query(rt[x], 1, n, k)]);
        }
    }
    return 0;
}